% el ignore ignora el c
\documentclass[ignorenonframetext]{beamer}

%\documentclass[11pt]{article}
%\usepackage{beamerarticle}

\mode<presentation>
{
  \usetheme{Warsaw}
  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}

\mode<article>
{
  \usepackage{fullpage}
  % \usepackage{pgf}
  \usepackage[colorlinks=true]{hyperref}
  % \setjobnamebeamerversion{beamerexample2.beamer}
}

\mode<handout>
{
   % cuando se arma la version entregable, se puede sacar algunos colores
   % que pueden molestar al imprimir
   \beamertemplatesolidbackgroundcolor{black!5}
}

\usepackage[english]{babel}
% \usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{graphics}

% \usepackage{listings}
% mis macros
\newcommand {\murl}[2]{\href{#1}{#2}}

\title[Programaci\'on gen\'etica: S\'intesis de un divisor
binario]{Programaci\'on gen\'etica: S\'intesis de un divisor binario}

\author[Sistemas Inteligentes, ITBA, 2010] {}


\date[Abril 2010] {Abril 2010. Revisi\'on 0 \\
 Licencia:
 \murl{http://creativecommons.org/licenses/by-sa/2.5/}{http://creativecommons.org/licenses/by-sa/2.5/
 }
}


\subject{Talks}

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}



 \AtBeginSubsection[]
 {
   \begin{frame}<beamer>
     \frametitle{Agenda}
     \tableofcontents[currentsection,currentsubsection]
  \end{frame}
 }


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Introducción}

 \begin{block} {Problema}
Se desea utilizar programación genética para diseñar utilizando compuertas lógicas un divisor entero de 4 bits para el dividendo y 2 bits para el divisor (sin tener en cuenta la división por cero).
 \end{block}
\end{frame}

\begin{frame}
  \frametitle{Introducción}
  \framesubtitle{Tabla de verdad}
     \begin{figure}[h]
         \begin{center}
            \includegraphics[width=3cm]{verdad.png}
         \end{center}
      \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Introducción}
  \framesubtitle{Tabla de verdad (orientada a bits)}
     \begin{figure}[h]
         \begin{center}
            \includegraphics[width=10cm]{verdad2.png}
         \end{center}
      \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Introducción}
  \framesubtitle{Tabla de verdad (representación más tradicional)}
     \begin{figure}[h]
         \begin{center}
            \includegraphics[width=5cm]{verdad3.png}
         \end{center}
      \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Introducción}
 \begin{block} {Como atacar el problema}
   \begin{itemize}
      \item Dividir el problema en 4 subproblemas similares independientes
      entre si: Encontrar un
      circuito lógico que respete una tabla de verdad de un bit de salida.
      ({\tt COCIENTE0, COCIENTE1, COCIENTE2,  COCIENTE3}).
   \end{itemize}
 \end{block}

\end{frame}

\begin{frame}
  \frametitle{Árboles Sintácticos}
 \begin{block}{Representación}
  \begin{itemize}
     \item Utilización de Árboles Sintácticos:
         \begin{itemize}
            \item {\tt TERMINALES = DIVISOR0 (a), DIVIDOR1 (b), DIVIDENDO0 (c),
            DIVIDENDO1 (d), DIVIDENDO2 (e) , DIVIDENDO3 (f)}
            \item {\tt OPERADORES = AND (\&), OR (|) , NOT (!)}
         \end{itemize}
  \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Árboles Sintácticos}
     \begin{figure}[h]
         \begin{center}
            \includegraphics[width=6cm]{../informe/arbol.pdf}
         \end{center}
         \caption{Árbol sintáctico para la expresión  {\tt \&|ab!b}. La
numeración marca el órden en que se visitan los nodos en un recorrido
pos-order.}
         \label{fig:arbol}
      \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Generación de la Población}

  \begin{itemize}
     \item {\em Full} (árboles completos de profundida máxima)
     \item {\em Grow} (árboles de profundad máxima)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Crossover y mutación}

  \begin{itemize}
     \item {\em Crossover} de punto simple (implementado con deep-copy + remplazo)
     \item {\em Mutación} utilizan la misma técnica de generación de la población
  \end{itemize}
\end{frame}


\begin{frame}
  \frametitle{Función Aptitud}
   \begin{block}{Definición}
    \begin{equation}
  2^n - distanciaHamming(resultados, evaluacion(expresion))
    \end{equation}
  \end{block}
   \begin{example}{Definición}
    \begin{itemize}
      \item {\em resultados}: Codominio de la tabla de verdad (Vector de bits)
      \item {\em expresion}: Árbol a evaluar
      \item {\em evaluacion(expresion)}: Resultado de evaluar la expresión para 
             todo el dominio de la tabla de verdad (Vector de bits)
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}
  \frametitle{Función Aptitud}

   \begin{block}{Premio a la soluciones simples}
      Si la aptitud es igual a $2^n$ entonces se le suma un término que premia
      soluciones corta: $1/longitud(expresion)$
  \end{block}
\end{frame}

\

\begin{frame}
  \frametitle{Función Aptitud}
  \framesubtitle{Evaluación}
     \begin{figure}
         \begin{center}
            \includegraphics[width=5cm]{../informe/arbol.pdf}
         \end{center}
      \end{figure}
      \begin{itemize}
       \item  {\tt S = [0011]}; {\tt S = [0011, 0101]}; POP, POP y {\tt S = [0111]};
       \item {\tt S = [0111, 0101]}; POP ; {\tt S = [0111, 1010]};
       \item POP, POP, {\tt S = [0010]}
    \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Reducción}
     \begin{block}{Teoremas del álgebra de conmutación con una variable}
   \begin{table}[h]
    \begin{center}
        \begin{tabular} {lclll}
           (T1)  & {\tt X | 0 = X}  &  &  (T1') {\tt X \& 1 = X} & Identidades \\
           (T2)  & {\tt X | 1 = 1}  &  &  (T2') {\tt X \& 0 = 0} & Elementos nulos \\
           (T3)  & {\tt X | X = X}  &  &  (T3') {\tt X \& X = X} & Potencias Idénticas \\
           (T4)  & {\tt !!X = X}    &  &                   & Involución  \\
           (T5)  & {\tt X |  !X = 1} &  &  (T5') {\tt X \& !X = 0} & Complementos \\
        \end{tabular}
    \end{center}
    \end{table}
    \end{block}
\end{frame}


\begin{frame}
  \frametitle{Reducción}
   Tres pasos:
   \begin{itemize}
     \item  recorrer el árbol de forma pos-order intentado
     aplicar las reglas de conmutación y modificando el árbol.
     Aquí se introducen dos  terminales nuevos {\tt TRUE, FALSE}
     \item evaluación pos-order + stack de la expresión (simil evaluación)
     aplicando las reglas (el arbol más corto gana)
     \item reemplazo de {\tt TRUE y FALSE}
   \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Simulación}
  \begin{block}{Algunos resultados}
    \begin{itemize}
     \item {\tt COCIENTE0: \&c!a}
     \item {\tt COCIENTE1: \&|!ac|d!b}
     \item {\tt COCIENTE2: \&|!b\&|\&cae!\&d\&ca||\&cbd!a}
     \item {\tt COCIENTE3: |\&e!b\&|fa||\&d\&!|ceb\&!d\&|cfe|\&!|!\&cf\&d!eb!a}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Simulación}
  \framesubtitle{Tabla de verdad (orientada a bits)}
     \begin{figure}[h]
         \begin{center}
            \includegraphics[width=10cm]{verdad2.png}
         \end{center}
      \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Resultados}
    \begin{itemize}

    \item Complejidad creciente ({\tt COCIENTE0 ... COCIENTE3}): 
          requiere mayor población inicial / iteraciones para resolver el problema.
    \item en general los métodos de selección {\tt elite+ruleta} y {\tt
         elite+universal} traen mejores resultados que {\tt ruleta} o {\tt universal}
         en combinación de elite como reemplazo.
    \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Resultados}
    \begin{itemize}
    \item {\tt COCIENTE0, COCIENTE1} con una población de 300 individuos
         resuelven siempre el problema en pocas iteraciones. Para esos casos
         tomar en la selección a toda la población ha hecho converger más
         rápidamente.
    \item {\tt COCIENTE2, COCIENTE3} Requiere por lo menos 2500 individuos. La
    selección es importante para la convergencia. Se puede producir un
    estancamiento de la población.

    \end{itemize}
\end{frame}



\end{document}


